// https://www.lintcode.com/problem/k-sum-ii

public class Solution {
    /**
     * @param A: an integer array
     * @param k: a postive integer <= length(A)
     * @param targer: an integer
     * @return: A list of lists of integer
     */
    public List<List<Integer>> kSumII(int[] A, int k, int target) {
        // write your code here
        List<List<Integer>> ret = new ArrayList<>();
        _kSumII(A, k, target, 0, ret, new ArrayList<>());
        return ret;
    }

    protected void _kSumII(int[] A, int k, int target, int idx, List<List<Integer>> ret, List<Integer> candidates) {
        if ((target == 0) && (k == 0)) {
            ret.add(candidates);
        } else if ((A.length == idx) || (target < 0) || (k < 0)) {
            return;
        } else {
            _kSumII(A, k, target, idx + 1, ret, candidates); // 跳过A[idx]
            List<Integer> new_candidates = new ArrayList<>();
            new_candidates.addAll(candidates);
            new_candidates.add(A[idx]);
            _kSumII(A, k - 1, target - A[idx], idx + 1, ret, new_candidates);
        }
    }
}